#include "mySearch.h"

SSTable::SSTable() : length(0), origin(nullptr) {}

SSTable::SSTable(int len, int* arr) : length(len), origin(new int[len]) {
    for (int i = 0; i < len; ++i) {
        origin[i] = arr[i];
    }
}

SSTable::~SSTable() {
    delete[] origin;
}

int SSTable::getLength() {
    return length;
}

int* SSTable::getOrigin() {
    return origin;
}

void SSTable::setLength(int len) {
    length = len;
}

void SSTable::setOrigin(int* arr) {
    if (origin) {
        delete[] origin;
    }
    origin = arr;
}

int SSTable::binSearch(int target) {
    int left = 0, right = length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (origin[mid] == target) {
            return mid;
        }
        if (origin[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

BSTreeNode::BSTreeNode() : data(0), lchild(nullptr), rchild(nullptr) {}

BSTreeNode::BSTreeNode(int val) : data(val), lchild(nullptr), rchild(nullptr) {}

BSTreeNode::BSTreeNode(int val, BSTreeNode* left, BSTreeNode* right) 
    : data(val), lchild(left), rchild(right) {}

BSTreeNode::~BSTreeNode() {}

int BSTreeNode::getData() {
    return data;
}

BSTreeNode* BSTreeNode::getLChild() {
    return lchild;
}

BSTreeNode* BSTreeNode::getRChild() {
    return rchild;
}

void BSTreeNode::setData(int val) {
    data = val;
}

void BSTreeNode::setLChild(BSTreeNode* left) {
    lchild = left;
}

void BSTreeNode::setRChild(BSTreeNode* right) {
    rchild = right;
}

BSTree::BSTree() : num(0), root(nullptr) {}

BSTree::BSTree(int n, int* arr) : num(n), root(nullptr) {
    for (int i = 0; i < n; ++i) {
        addNode(arr[i]);
    }
}

BSTree::~BSTree() {
    delete root;
}

int BSTree::getNum() {
    return num;
}

BSTreeNode* BSTree::getRoot() {
    return root;
}

void BSTree::setRoot(BSTreeNode* node) {
    root = node;
}

void BSTree::setNum(int n) {
    num = n;
}

string BSTree::printTree() {
    string result;
    printTreeHelper(root, result);
    return result;
}

void BSTree::printTreeHelper(BSTreeNode* node, string& result) {
    if (!node) return;
    result += to_string(node->getData()) + " ";
    printTreeHelper(node->getLChild(), result);
    printTreeHelper(node->getRChild(), result);
}

bool BSTree::searchNode(int val) {
    return searchNodeHelper(root, val);
}

bool BSTree::searchNodeHelper(BSTreeNode* node, int val) {
    if (!node) return false;
    if (node->getData() == val) return true;
    if (val < node->getData())
        return searchNodeHelper(node->getLChild(), val);
    return searchNodeHelper(node->getRChild(), val);
}

bool BSTree::addNode(int val) {
    if (!root) {
        root = new BSTreeNode(val);
        ++num;
        return true;
    }
    return addNodeHelper(root, val);
}

bool BSTree::addNodeHelper(BSTreeNode* node, int val) {
    if (val < node->getData()) {
        if (!node->getLChild()) {
            node->setLChild(new BSTreeNode(val));
            ++num;
            return true;
        }
        return addNodeHelper(node->getLChild(), val);
    } else if (val > node->getData()) {
        if (!node->getRChild()) {
            node->setRChild(new BSTreeNode(val));
            ++num;
            return true;
        }
        return addNodeHelper(node->getRChild(), val);
    }
    return false; // Duplicate value
}

bool BSTree::deleteNode(int val) {
    if (searchNode(val)) {
        root = deleteNodeHelper(root, val);
        --num;
        return true;
    }
    return false;
}

BSTreeNode* BSTree::deleteNodeHelper(BSTreeNode* node, int val) {
    if (!node) return nullptr;

    if (val < node->getData()) {
        node->setLChild(deleteNodeHelper(node->getLChild(), val));
    } else if (val > node->getData()) {
        node->setRChild(deleteNodeHelper(node->getRChild(), val));
    } else {
        if (!node->getLChild()) {
            BSTreeNode* temp = node->getRChild();
            delete node;
            return temp;
        } else if (!node->getRChild()) {
            BSTreeNode* temp = node->getLChild();
            delete node;
            return temp;
        }

        BSTreeNode* temp = minValueNode(node->getRChild());
        node->setData(temp->getData());
        node->setRChild(deleteNodeHelper(node->getRChild(), temp->getData()));
    }
    return node;
}

BSTreeNode* BSTree::minValueNode(BSTreeNode* node) {
    BSTreeNode* current = node;
    while (current && current->getLChild()) {
        current = current->getLChild();
    }
    return current;
}